Packet classification is used in a wide variety of contexts and for a wide variety of purposes. In general, packet classification is typically performed by matching header fields of incoming packets against a set of candidate packet classification rules in order to determine proper handling of each packet (e.g., performing a particular type of processing on the packet, forwarding the packet to a given next hop, dropping the packet, or the like). In many cases, packet classification needs to be performed across multiple network protocol layers (e.g., layers (Ls) of the Transmission Control Protocol (TCP)/Internet Protocol (IP) model) based on information from multiple network protocol layers. This is often referred to as multi-layer packet classification. For example, several types of network equipment implement multi-layer packet classification which may operate on fields from the data link, network, and transport layers, such as firewalls (e.g., operating on L2-L4 of the TCP/IP model), network address translators (e.g., operating on L3-L4 of the TCP/IP model), virtual switches in software defined networks (e.g., operating on L2-L4 of the TCP/IP), and so forth.
Many packet classification schemes are currently implemented via specialized hardware, such as ternary content-addressable memory (TCAM), in order to satisfy strict speed requirements. However, the availability of powerful commodity hardware, coupled with the high cost, limited storage, and high power consumption of TCAM, have sparked new interest in fast software-based packet classification. Additionally, recent developments in virtualized environments (e.g., multi-tenant networks, network function virtualization, and the like) have resulted in widespread adoption of virtual switches, which typically include software programs that classify packets. Many virtualized environments are operating at speeds that require throughputs of 10 Gbps or greater in order to avoid bottlenecks and delays, such that software-based packet classification speeds need to be improved in order to support such throughput requirements. Additionally, the recent emergence of software defined networking (SDN), which has a strong emphasis on rule-based flow classification and packet processing, also is driving a need for faster software-based packet classification. For example, in SDN based on OpenFlow, the relatively large rule tables and the relatively long multi-dimensional OpenFlow tuples may impose unforeseen challenges for current software-based packet classifiers that cannot be easily addressed by hardware-based packet classification schemes.
Accordingly, in view of these and various other developments related to use of software-based packet classification schemes and packet classification schemes in general, there is a renewed interest in and need for improved packet classification schemes.